using AnimCollections;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Mathematics;
using UnityEngine;

namespace DA.AnimGraph {

    // 此结构由于含有 NativeArray，导致不能序列化，所以提供一个一模一样的用于序列化的版本
    public struct TriangulationData : IDisposable {
        [StructLayout(LayoutKind.Sequential)]
        public unsafe struct Triangle {
            //public fixed int clipID[3]; // 在最初 AddVertices 时数组中的序号，一般来说对应外部 clip 数组中的序号
            [SerializeField] int clipId_0;
            [SerializeField] int clipId_1;
            [SerializeField] int clipId_2;
            //public fixed int edgeId[3]; // 在edges中的id
            [SerializeField] int edgeId_0;
            [SerializeField] int edgeId_1;
            [SerializeField] int edgeId_2;
            //public fixed float Vertices[6]; // 三组顶点坐标，已归一化
            [SerializeField] float2 vertices_0;
            [SerializeField] float2 vertices_1;
            [SerializeField] float2 vertices_2;

            public int* clipId {
                get {
                    fixed (int* p = &clipId_0)
                        return p;
                }
            }
            public int* edgeId {
                get {
                    fixed (int* p = &edgeId_0)
                        return p;
                }
            }
            public float2* vertices {
                get {
                    fixed (float2* p = &vertices_0)
                        return p;
                }
            }
        }

        public struct Edge {
            public float2 normal; //垂直于此边且向外的单位向量
            public int neighbourTriangleId; //相邻三角形id
            public int2 adjacentPerimeterTriangleId; //代替数组,外周上相邻三角形的id
            public int2 adjacentPerimeterVertexId; //代替数组,外周上相邻顶点的id
        }

        public float2 gridMin;
        public float2 gridScale;
        public NativeSimpleArray<Triangle> triangles;
        public NativeSimpleArray<Edge> edges;

        public void Dispose() {
            triangles.Dispose();
            edges.Dispose();
        }
    }

    public struct TriangulationDataSerializable {
        public float2 gridMin;
        public float2 gridScale;
        public TriangulationData.Triangle[] triangles;
        public TriangulationData.Edge[] edges;

        public TriangulationData ToNative(ref GraphBuffer buffer) {
            var result = new TriangulationData() {
                gridMin = gridMin,
                gridScale = gridScale,
            };
            buffer.MallocNativeSimpleArray(out result.triangles, triangles);
            buffer.MallocNativeSimpleArray(out result.edges, edges);
            return result;
        }
    }

    public class Triangulation {
        private class Vertex {
            public Vector2 pos;
            public int srcId;
            public int clipId;
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public static bool IsEqual(Vertex lhs, Vertex rhs) {
                return lhs.pos == rhs.pos;
            }
        }
        private class Edge {
            public Vertex[] vertex = new Vertex[2];
            public Edge(Vertex a, Vertex b) {
                vertex[0] = a;
                vertex[1] = b;
            }

            public static bool IsSame(Edge lhs, Edge rhs) {
                return Vertex.IsEqual(lhs.vertex[0], rhs.vertex[0]) && Vertex.IsEqual(lhs.vertex[1], rhs.vertex[1]);
            }
            public static bool IsCollinear(Edge lhs, Edge rhs) {
                return (Vertex.IsEqual(lhs.vertex[0], rhs.vertex[0]) && Vertex.IsEqual(lhs.vertex[1], rhs.vertex[1]))
                    || (Vertex.IsEqual(lhs.vertex[0], rhs.vertex[1]) && Vertex.IsEqual(lhs.vertex[1], rhs.vertex[0]));
            }
        }
        private class Triangle {
            public Vertex[] vertices = new Vertex[3];
            public Edge[] edges = new Edge[3];

            public Triangle(Vertex A, Vertex B, Vertex C) {
                vertices[0] = A;
                vertices[1] = B;
                vertices[2] = C;

                MakeCCW();

                edges[0] = new Edge(vertices[0], vertices[1]);
                edges[1] = new Edge(vertices[1], vertices[2]);
                edges[2] = new Edge(vertices[2], vertices[0]);
            }
            public Triangle(Vertex A, Vertex B) {
                vertices[0] = A;
                vertices[1] = B;
                vertices[2] = B;

                edges[0] = new Edge(vertices[0], vertices[1]);
                edges[1] = new Edge(vertices[1], vertices[2]);
                edges[2] = new Edge(vertices[2], vertices[0]);
            }
            public Triangle(Vertex A) {
                vertices[0] = A;
                vertices[1] = A;
                vertices[2] = A;

                edges[0] = new Edge(vertices[0], vertices[1]);
                edges[1] = new Edge(vertices[1], vertices[2]);
                edges[2] = new Edge(vertices[2], vertices[0]);
            }

            public bool HasSameEdge(Triangle other) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (Edge.IsSame(other.edges[i], edges[j])) return true;
                    }
                }
                return false;
            }
            public bool HasCollinearEdge(Triangle other) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (Edge.IsCollinear(other.edges[i], edges[j])) return true;
                    }
                }
                return false;
            }
            public Vertex FindNonSharingPoint(Triangle other) {
                if (!vertices.Contains(other.vertices[0])) return other.vertices[0];
                if (!vertices.Contains(other.vertices[1])) return other.vertices[1];
                if (!vertices.Contains(other.vertices[2])) return other.vertices[2];
                return null;
            }
            private void MakeCCW() {
                Vector2 dir1 = vertices[1].pos - vertices[0].pos;
                Vector2 dir2 = vertices[2].pos - vertices[0].pos;
                var final = dir1.x * dir2.y - dir1.y * dir2.x;
                if (final < 0) {
                    Vertex tmp = vertices[1];
                    vertices[1] = vertices[2];
                    vertices[2] = tmp;
                }
            }
        }

        List<Vertex> vertices;//输入的顶点
        List<Triangle> triangleList;//存储三角剖分的结果
        Vector2 gridMin;//分布点的最小值
        Vector2 gridScale;//分布点范围归一化的缩放比例

        // 参数两个List成员数量要一致
        // clipIds成员代表引用资源下标，相同下标代表同一资源
        // 下标从0开始，不能间断，例如： 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 8, 8 
        public void AddVertices(List<Vector2> inVertics, List<int> clipIds) {
            vertices = new(inVertics.Count);
            Vector2 min = new Vector2();
            Vector2 max = new Vector2();

            for (int i = 0; i < inVertics.Count; i++) {
                vertices.Add(new Vertex {
                    pos = inVertics[i],
                    srcId = i,
                    clipId = clipIds[i],
                });
                min.x = Mathf.Min(min.x, inVertics[i].x);
                min.y = Mathf.Min(min.y, inVertics[i].y);
                max.x = Mathf.Max(max.x, inVertics[i].x);
                max.y = Mathf.Max(max.y, inVertics[i].y);
            }
            SetGrid(min, max);
            vertices = vertices.OrderBy(p => p.pos.y).ThenBy(p => p.pos.x).ToList();
        }

        public void Triangulate() {
            triangleList = new();
            if (vertices.Count == 0) return;
            if (vertices.Count == 1) {
                AddTriangle(new Triangle(vertices[0]));
            } else if (vertices.Count == 2) {
                AddTriangle(new Triangle(vertices[0], vertices[1]));
            } else {
                for (int i = 3; i <= vertices.Count; i++) {
                    if (i == 3) {
                        if (IsNotCollinear(vertices[0], vertices[1], vertices[2])) {
                            AddTriangle(new Triangle(vertices[0], vertices[1], vertices[2]));
                        }
                    } else if (triangleList.Count == 0) {
                        Vertex tmp = vertices[i - 1];
                        for (int j = 0; j < i - 2; j++) {
                            if (IsNotCollinear(vertices[j], vertices[j + 1], tmp)) {
                                AddTriangle(new Triangle(vertices[j], vertices[j + 1], tmp));
                            }
                        }
                    } else {
                        Vertex tmp = vertices[i - 1];
                        int count = triangleList.Count;
                        for (int j = 0; j < count; j++) {
                            var tmpTriangle = triangleList[j];
                            if (IsNotCollinear(tmpTriangle.vertices[0], tmpTriangle.vertices[1], tmp)) {
                                AddTriangle(new Triangle(tmpTriangle.vertices[0], tmpTriangle.vertices[1], tmp));
                            }
                            if (IsNotCollinear(tmpTriangle.vertices[0], tmpTriangle.vertices[2], tmp)) {
                                AddTriangle(new Triangle(tmpTriangle.vertices[0], tmpTriangle.vertices[2], tmp));
                            }
                            if (IsNotCollinear(tmpTriangle.vertices[1], tmpTriangle.vertices[2], tmp)) {
                                AddTriangle(new Triangle(tmpTriangle.vertices[1], tmpTriangle.vertices[2], tmp));
                            }
                        }

                        for (int z = 0; z < triangleList.Count; z++) {
                            var A = triangleList[z];
                            for (int w = z + 1; w < triangleList.Count; w++) {
                                var B = triangleList[w];
                                if (A.HasCollinearEdge(B)) {
                                    if (FlipTriangles(A, B)) {
                                        triangleList.Remove(B);
                                        triangleList.Remove(A);
                                        z = -1;
                                        break;
                                    }
                                }
                            }
                        }

                    }
                }

                //
                if (triangleList.Count == 0) {
                    if (IsAllSamePoint(vertices)) {
                        AddTriangle(new Triangle(vertices[0]));
                    } else {
                        for (int i = 1; i < vertices.Count; i++) {
                            AddTriangle(new Triangle(vertices[i - 1], vertices[i]));
                        }
                    }
                }
            }
            //
            AdjustEdgeDirections();
        }

        /*
        public unsafe void OutputToData(out TriangulationData outData) {
            outData.gridMin = gridMin;
            outData.gridScale = gridScale;

            outData.triangles = new NativeArray<TriangulationData.Triangle>(triangleList.Count, Allocator.Persistent);
            outData.edges = new NativeArray<TriangulationData.Edge>(triangleList.Count * 3, Allocator.Persistent);

            for (int i = 0; i < triangleList.Count; i++) {
                var tri = triangleList[i];
                outData.triangles[i] = new TriangulationData.Triangle();
                ref var newTri = ref outData.triangles.GetRefAt(i);

                Vector2[] normalizedVertices = new Vector2[3];
                normalizedVertices[0] = (tri.vertices[0].pos - gridMin) * gridScale;
                normalizedVertices[1] = (tri.vertices[1].pos - gridMin) * gridScale;
                normalizedVertices[2] = (tri.vertices[2].pos - gridMin) * gridScale;

                for (int j = 0; j < 3; j++) {
                    newTri.vertices[j] = normalizedVertices[j];
                    newTri.clipId[j] = tri.vertices[j].clipId;
                }

                for (int edgeId = 0; edgeId < 3; edgeId++) {
                    outData.edges[i * 3 + edgeId] = new TriangulationData.Edge();
                    ref var edge = ref outData.edges.GetRefAt(i * 3 + edgeId);
                    int edgeIdNext = (edgeId + 1) % 3;

                    edge.neighbourTriangleId = FindTriangleIndexWithEdge(tri.vertices[edgeIdNext].srcId, tri.vertices[edgeId].srcId, out int eintri);

                    Vector2 edgeDir = normalizedVertices[edgeIdNext] - normalizedVertices[edgeId];
                    edge.normal = new Vector2(edgeDir.y, -edgeDir.x).normalized;

                    edge.adjacentPerimeterTriangleId = new(-1, -1);
                    edge.adjacentPerimeterVertexId = new(-1, -1);

                    newTri.edgeId[edgeId] = i * 3 + edgeId;
                }
            }

            for (int i = 0; i < outData.triangles.Length; i++) {
                ref var tri = ref outData.triangles.GetRefAt(i);
                for (int edgeId = 0; edgeId < 3; edgeId++) {
                    ref var edge = ref outData.edges.GetRefAt(tri.edgeId[edgeId]);
                    if (edge.neighbourTriangleId == -1) {
                        int edgeIdNext = (edgeId + 1) % 3;

                        for (int j = 0; j < outData.triangles.Length; j++) {
                            if (i == j) continue;

                            var otherTri = outData.triangles[j];

                            for (int otherMotionId = 0; otherMotionId < 3; otherMotionId++) {
                                int otherMotionIdPrev = (otherMotionId + 2) % 3;

                                if (otherTri.clipId[otherMotionId] == tri.clipId[edgeId]
                                    && outData.edges[otherTri.edgeId[otherMotionIdPrev]].neighbourTriangleId == -1) {
                                    edge.adjacentPerimeterTriangleId.x = j;
                                    edge.adjacentPerimeterVertexId.x = otherMotionIdPrev;
                                }
                                if (otherTri.clipId[otherMotionId] == tri.clipId[edgeIdNext]
                                   && outData.edges[otherTri.edgeId[otherMotionId]].neighbourTriangleId == -1) {
                                    edge.adjacentPerimeterTriangleId.y = j;
                                    edge.adjacentPerimeterVertexId.y = otherMotionId;
                                }
                            }
                        }
                    }
                }
            }
        }
        */

        public unsafe void OutputToData(out TriangulationDataSerializable outData) {
            outData.gridMin = gridMin;
            outData.gridScale = gridScale;

            outData.triangles = new TriangulationData.Triangle[triangleList.Count];
            outData.edges = new TriangulationData.Edge[triangleList.Count * 3];

            for (int i = 0; i < triangleList.Count; i++) {
                var tri = triangleList[i];
                var newTri = new TriangulationData.Triangle();

                Vector2[] normalizedVertices = new Vector2[3];
                normalizedVertices[0] = (tri.vertices[0].pos - gridMin) * gridScale;
                normalizedVertices[1] = (tri.vertices[1].pos - gridMin) * gridScale;
                normalizedVertices[2] = (tri.vertices[2].pos - gridMin) * gridScale;

                for (int j = 0; j < 3; j++) {
                    newTri.vertices[j] = normalizedVertices[j];
                    newTri.clipId[j] = tri.vertices[j].clipId;
                }

                for (int edgeId = 0; edgeId < 3; edgeId++) {
                    var edge = new TriangulationData.Edge();

                    int edgeIdNext = (edgeId + 1) % 3;

                    edge.neighbourTriangleId = FindTriangleIndexWithEdge(tri.vertices[edgeIdNext].srcId, tri.vertices[edgeId].srcId, out int eintri);

                    Vector2 edgeDir = normalizedVertices[edgeIdNext] - normalizedVertices[edgeId];
                    edge.normal = new Vector2(edgeDir.y, -edgeDir.x).normalized;

                    edge.adjacentPerimeterTriangleId = new(-1, -1);
                    edge.adjacentPerimeterVertexId = new(-1, -1);

                    newTri.edgeId[edgeId] = i * 3 + edgeId;
                    outData.edges[i * 3 + edgeId] = edge;
                }

                outData.triangles[i] = newTri;
            }

            for (int i = 0; i < outData.triangles.Length; i++) {
                var tri = outData.triangles[i];

                for (int edgeId = 0; edgeId < 3; edgeId++) {
                    var edge = outData.edges[tri.edgeId[edgeId]];

                    if (edge.neighbourTriangleId == -1) {
                        int edgeIdNext = (edgeId + 1) % 3;

                        for (int j = 0; j < outData.triangles.Length; j++) {
                            if (i == j) continue;

                            var otherTri = outData.triangles[j];

                            for (int otherMotionId = 0; otherMotionId < 3; otherMotionId++) {
                                int otherMotionIdPrev = (otherMotionId + 2) % 3;

                                if (otherTri.clipId[otherMotionId] == tri.clipId[edgeId]
                                    && outData.edges[otherTri.edgeId[otherMotionIdPrev]].neighbourTriangleId == -1) {
                                    edge.adjacentPerimeterTriangleId.x = j;
                                    edge.adjacentPerimeterVertexId.x = otherMotionIdPrev;
                                }
                                if (otherTri.clipId[otherMotionId] == tri.clipId[edgeIdNext]
                                   && outData.edges[otherTri.edgeId[otherMotionId]].neighbourTriangleId == -1) {
                                    edge.adjacentPerimeterTriangleId.y = j;
                                    edge.adjacentPerimeterVertexId.y = otherMotionId;
                                }
                            }
                        }
                    }

                    outData.edges[tri.edgeId[edgeId]] = edge;
                }

                outData.triangles[i] = tri;
            }
        }

        void SetGrid(Vector2 min, Vector2 max) {
            gridMin = min;
            Vector2 range = max - min;
            gridScale = Vector2.one / range;
        }

        /// <summary>
        /// 翻转以修正分割线
        /// </summary>
        private void AdjustEdgeDirections() {
            // 暂且只提供切向方法
            for (int id0 = 0; id0 < triangleList.Count; id0++) {
                Triangle tri0 = triangleList[id0];
                int edgeId0 = GetCandidateEdgeIndex(tri0);
                if (edgeId0 >= 0) {
                    int edgeNextId0 = (edgeId0 + 1) % 3;
                    Vector2 edgeDir = tri0.vertices[edgeNextId0].pos - tri0.vertices[edgeId0].pos;
                    Vector2 edgePos = (tri0.vertices[edgeNextId0].pos + tri0.vertices[edgeId0].pos) * 0.5f;
                    bool isUp = edgeDir.x * edgeDir.y > 0;
                    bool isDesiredUp = edgePos.x * edgePos.y < 0;

                    if (isUp == isDesiredUp) continue;

                    int sampleStartId = tri0.vertices[edgeId0].srcId;
                    int sampleEndId = tri0.vertices[edgeNextId0].srcId;
                    int edgeId1;
                    int triId1 = FindTriangleIndexWithEdge(sampleEndId, sampleStartId, out edgeId1);
                    if (triId1 < 0) continue;
                    Triangle tri1 = triangleList[triId1];
                    if (GetCandidateEdgeIndex(tri1) == edgeId1) {
                        int edgePrevId1 = (edgeId1 + 2) % 3;
                        int edgeNextId1 = (edgeId1 + 1) % 3;
                        int edgePrevId0 = (edgeId0 + 2) % 3;

                        tri0.vertices[edgeNextId0] = tri1.vertices[edgePrevId1];
                        tri1.vertices[edgeNextId1] = tri0.vertices[edgePrevId0];
                    }
                }
            }
        }

        /// <summary>
        /// 查找三角形斜边（其它两边为水平和垂直）
        /// </summary>
        private int GetCandidateEdgeIndex(Triangle tri) {
            bool isFoundVert = false;
            bool isFoundHor = false;
            bool isFoundSlope = false;
            int slopeIndex = 0;
            for (int vertexIndex = 0; vertexIndex != 3; ++vertexIndex) {
                int vertexIndexNext = (vertexIndex + 1) % 3;
                if (tri.vertices[vertexIndex].pos.x == tri.vertices[vertexIndexNext].pos.x) {
                    isFoundVert = true;
                } else if (tri.vertices[vertexIndex].pos.y == tri.vertices[vertexIndexNext].pos.y) {
                    isFoundHor = true;
                } else {
                    isFoundSlope = true;
                    slopeIndex = vertexIndex;
                }
            }
            if (isFoundVert && isFoundHor && isFoundSlope) {
                return slopeIndex;
            } else {
                return -1;
            }
        }
        int FindTriangleIndexWithEdge(int srcId0, int srcId1, out int edgeId) {
            for (int i = 0; i < triangleList.Count; i++) {
                var tir = triangleList[i];
                if (tir.vertices[0].srcId == srcId0 && tir.vertices[1].srcId == srcId1) {
                    edgeId = 0;
                    return i;
                }
                if (tir.vertices[1].srcId == srcId0 && tir.vertices[2].srcId == srcId1) {
                    edgeId = 1;
                    return i;
                }
                if (tir.vertices[2].srcId == srcId0 && tir.vertices[0].srcId == srcId1) {
                    edgeId = 2;
                    return i;
                }
            }

            edgeId = -1;
            return -1;
        }

        private bool FlipTriangles(Triangle A, Triangle B) {
            Vertex tmp = A.FindNonSharingPoint(B);
            if (tmp == null) return false;
            if (GetCircumcircleState(A, tmp) >= 0) {
                return false;
            }

            List<Triangle> newTriList = new(2);
            for (int i = 0; i < 2; i++) {
                for (int j = i + 1; j < 3; j++) {
                    if (IsNotCollinear(A.vertices[i], A.vertices[j], tmp)) {
                        var newTri = new Triangle(A.vertices[i], A.vertices[j], tmp);
                        int otherVertexId = 3 - i - j;
                        if (GetCircumcircleState(newTri, A.vertices[otherVertexId]) == 1) {
                            newTriList.Add(newTri);
                        }
                    }
                }
            }

            if (newTriList.Count == 2) {
                triangleList.Add(newTriList[0]);
                triangleList.Add(newTriList[1]);
                return true;
            }
            return false;
        }
        /// <summary>
        /// 检测点与三角形外接圆的位置关系
        /// 返回 -1：内，0：上，1：外
        /// </summary>
        private int GetCircumcircleState(Triangle t, Vertex p) {
            Vector2[] NormalizedPositions = new Vector2[3];

            NormalizedPositions[0] = (t.vertices[0].pos - gridMin) * gridScale;
            NormalizedPositions[1] = (t.vertices[1].pos - gridMin) * gridScale;
            NormalizedPositions[2] = (t.vertices[2].pos - gridMin) * gridScale;

            Vector2 NormalizedTestPoint = (p.pos - gridMin) * gridScale;

            double M00 = NormalizedPositions[0].x - NormalizedTestPoint.x;
            double M01 = NormalizedPositions[0].y - NormalizedTestPoint.y;
            double M02 = NormalizedPositions[0].x * NormalizedPositions[0].x - NormalizedTestPoint.x * NormalizedTestPoint.x
               + NormalizedPositions[0].y * NormalizedPositions[0].y - NormalizedTestPoint.y * NormalizedTestPoint.y;

            double M10 = NormalizedPositions[1].x - NormalizedTestPoint.x;
            double M11 = NormalizedPositions[1].y - NormalizedTestPoint.y;
            double M12 = NormalizedPositions[1].x * NormalizedPositions[1].x - NormalizedTestPoint.x * NormalizedTestPoint.x
               + NormalizedPositions[1].y * NormalizedPositions[1].y - NormalizedTestPoint.y * NormalizedTestPoint.y;

            double M20 = NormalizedPositions[2].x - NormalizedTestPoint.x;
            double M21 = NormalizedPositions[2].y - NormalizedTestPoint.y;
            double M22 = NormalizedPositions[2].x * NormalizedPositions[2].x - NormalizedTestPoint.x * NormalizedTestPoint.x
                + NormalizedPositions[2].y * NormalizedPositions[2].y - NormalizedTestPoint.y * NormalizedTestPoint.y;

            double det = M00 * M11 * M22 + M01 * M12 * M20 + M02 * M10 * M21 - (M02 * M11 * M20 + M01 * M10 * M22 + M00 * M12 * M21);

            if (det < 0) return 1;
            if (det == 0) return 0;
            return -1;
        }
        void AddTriangle(Triangle t) {
            foreach (var p in triangleList) {
                if (p == t) return;
                if (p.HasSameEdge(t)) return;
            }
            triangleList.Add(t);
        }

        bool IsNotCollinear(Vertex A, Vertex B, Vertex C) {
            Vector2 dir1 = B.pos - A.pos;
            Vector2 dir2 = C.pos - A.pos;
            var final = dir1.x * dir2.y - dir1.y * dir2.x;
            return final != 0;
        }
        bool IsAllSamePoint(List<Vertex> vertices) {
            var first = vertices[0];
            for (int i = 1; i < vertices.Count; i++) {
                if (!Vertex.IsEqual(first, vertices[i])) {
                    return false;
                }
            }
            return true;
        }
    }
}
